#include <cstdio>
#include <iostream>

using namespace std;

int arr[21], n = 0;

template<class K>
struct Node {
    Node(K k) {
        key = k;
		parent = NULL;
		left = NULL;
		right = NULL;
    }
    Node<K>* parent;
    Node<K>* left;
    Node<K>* right;
    K key;
};

void input() {
    int x;
    cin >> x;

    while (x !=0) {
        arr[++n] = x;
        cin >> x;
    }
}

void output(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        cout << *(arr + i) << ",";
    }
    cout << *(arr + size - 1) << endl;
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void createMaxHeap(int* arr, int n) {
    for(int i = n / 2; i >= 1; i--) {
        int val = arr[i];
        int pos = 2 * i;
        while (pos <= n) {
            if (pos < n && arr[pos] < arr[pos + 1]) {
                pos++;
            }
            if (val > arr[pos]) {
                break;
            } else {
                arr[pos / 2] = arr[pos];
                pos *= 2;
            }
        }

        arr[pos / 2] = val;
    }
}

void heapSort(int* arr, int n) {
    for (int i = 1; i <= n; i++) {
        createMaxHeap(arr, n - i + 1);
        swap(arr + 1, arr + n - i + 1);
    }
    output(arr + 1, n);
}

template<class T>
void insert(Node<T>* head, Node<T>* node) {
    Node<T>* temp = head;
    if (temp == NULL) {
        head = node;
        return;
    }
    while (1) {
        if (temp->key > node->key) {
            if (temp->left != NULL) {
                temp = temp->left;
            } else {
                temp->left = node;
                node->parent = temp;
                return;
            }
        } else if (temp->key < node->key) {
            if (temp->right != NULL) {
                temp = temp->right;
            } else {
                temp->right = node;
                node->parent = temp;
                return;
            }
        } else break;
    }
}

Node<int>* createBSTree(int* arr, int n) {
    Node<int>* head = new Node<int>(*(arr + 1));

    for (int i = 2; i <= n; i++) {
        // Insert into tree
        Node<int>* node = new Node<int>(*(arr + i));
        insert(head, node);
    }

    return head;
}

int po[21];
template<class T>
void preOrder(Node<T>* head) {
    if (head == NULL) return;
    po[++po[0]] = head->key;

    if (head->left != NULL) preOrder(head->left);
    if (head->right != NULL) preOrder(head->right);
}

int io[21];
template<class T>
void inOrder(Node<T>* head) {
    if (head == NULL) return;
    if (head->left != NULL) inOrder(head->left);
    io[++io[0]] = head->key;
    if (head->right != NULL) inOrder(head->right);
}

int main()
{
    int i;
    cout << "Input" << endl;
    input();
    cout << "Output" << endl;
    int heap[21];
    for (i = 1; i <= n; i++) heap[i] = arr[i];
    createMaxHeap(heap, n);
    output(heap + 1, n);
    heapSort(heap, n);

    // BSTree
    Node<int>* head = createBSTree(arr, n);
    po[0] = 0;
    preOrder(head);
    output(po + 1, po[0]);

    io[0] = 0;
    inOrder(head);
    output(io + 1, io[0]);
    cout << "End" << endl;
    return 0;
}
